package star.基础.归并排序;

import star.Utils;

import javax.print.DocFlavor;

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {4,6,8,5,2,9,1,5,7};
        process(arr,0,8);
        Utils.traversal(arr);
    }

    private static void process(int[] arr,int L,int R){
        if (L==R) return;
        int mid = L + ((R - L) >> 1);
        process(arr,L,mid);
        process(arr,mid+1,R);
        merge(arr,L,mid,R);
    }

    private static void merge(int[] arr, int L, int M, int R) {
        int[] help = new int[R-L+1];
        int i = 0;
        int l = L;
        int r = M+1;
        while (l <= M && r <= R){
            help[i++] = arr[l] <= arr[r] ? arr[l++] : arr[r++];
        }
        while (l <= M){
            help[i++] = arr[l++];
        }
        while (r <= R){
            help[i++] = arr[r++];
        }
        for (int j = 0; j < help.length; j++) {
            arr[L+j] = help[j];
        }
    }

}
